| |
| description |
22 pages
|
|
We study the complexity of the confluence problem for restricted
kinds of semi--Thue systems, vector replacement systems and general
trace rewriting systems. We prove that confluence for
length--reducing semi--Thue systems is P--complete and that this
complexity reduces to $\AC^1$ in the monadic case (where all
right--hand sides consist of at most one symbol). For
length--reducing vector replacement systems we prove that the
confluence problem is PSPACE--complete and that the complexity
reduces to NP and P, respectively, for monadic vector replacement
systems and special vector replacement systems (where all
right--hand sides are empty), respectively. Finally we prove that
for special trace rewriting systems, confluence can be decided in
polynomial time and that the extended word problem for special trace
rewriting systems is undecidable
|
| publisher |
Stuttgart, Germany, Universität Stuttgart
|
| type |
Text
|
| Technical Report
|
| source |
ftp://ftp.informatik.uni-stuttgart.de/pub/library/ncstrl.ustuttgart_fi/TR-1999-05/TR-1999-05.pdf
|
| contributor |
Theoretische Informatik (IFI)
|
| format |
application/pdf
|
| subject |
Grammars and Other Rewriting Systems (CR F.4.2)
|
| Formal Languages (CR F.4.3)
|
| relation |
Technical Report No. 1999/05
|